package com.yusong.algorithm.stack;

import com.yusong.algorithm.array.Index3Sort;

import java.util.*;

/**
 * 有效的括号
 */
public class Bracket20 {

    public static void main(String[] args) {

        Bracket20 main = new Bracket20();

        main.isValid("]");

    }


    //只包括 '('，')'，'{'，'}'，'['，']'
    private static Map<Character,Character> BRACKET_MAP = new HashMap();
    private static Set<Character> SET = BRACKET_MAP.keySet();
    static {
        BRACKET_MAP.put(')','(');
        BRACKET_MAP.put('}','{');
        BRACKET_MAP.put(']','[');
    }

    public boolean isValid(String s) {
        if(s == null || "".equals(s)){
            return true;
        }
        //推荐使用Deque来模拟栈
        Deque<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for(Character c : chars){
            //左括号进栈，右括号取出
            if(SET.contains(c)){
                Character popC = stack.pollFirst();
                if(popC != null && popC.equals(BRACKET_MAP.get(c))){
                    continue;
                }else {
                    return false;
                }
            }else {
                stack.push(c);
            }

        }
        return stack.size() == 0;
    }




}
